Stone game II

Time: O(Nx(LogN)^2); Space: O(NLogN); medium

Alex and Lee continue their games with piles of stones. There are a number of piles arranged in a row, and each pile has a positive integer number of stones piles[i]. The objective of the game is to end with the most stones.

Alex and Lee take turns, with Alex starting first. Initially, M = 1.

On each player’s turn, that player can take all the stones in the first X remaining piles, where 1 <= X <= 2M. Then, we set M = max(M, X).

The game continues until all the stones have been taken.

Assuming Alex and Lee play optimally, return the maximum number of stones Alex can get.

Example 1:

Input: piles = [2,7,9,4,4]

Output: 10

Explanation:

  • If Alex takes one pile at the beginning, Lee takes two piles, then Alex takes 2 piles again.

  • Alex can get 2 + 4 + 4 = 10 piles in total.

  • If Alex takes two piles at the beginning, then Lee can take all three piles left.

  • In this case, Alex get 2 + 7 = 9 piles in total.

  • So we return 10 since it’s larger.

Constraints:

  • 1 <= len(piles) <= 100

  • 1 <= piles[i] <= 10 ^ 4

Hints:

  1. Use dynamic programming: the states are (i, m) for the answer of piles[i:] and that given m.

1. Dynamic programming [O(Nx(LogN)^2), O(NLogN)]

[1]:

class Solution1(object):
    """
    Time: O(N*(LogN)^2)
    Space: O(NLogN)
    """
    def stoneGameII(self, piles):
        """
        :type piles: List[int]
        :rtype: int
        """
        def dp(piles, lookup, i, m):
            if i+2*m >= len(piles):
                return piles[i]
            if (i, m) not in lookup:
                lookup[i, m] = piles[i] - min(dp(piles, lookup, i+x, max(m, x))
                                              for x in range(1, 2*m+1))
            return lookup[i, m]

        for i in reversed(range(len(piles)-1)):
            piles[i] += piles[i+1]

        return dp(piles, {}, 0, 1)

[2]:

s = Solution1()

piles =  [2,7,9,4,4]
assert s.stoneGameII(piles) == 10